import java.util.Stack;

public class ReversePrint {
    //法1
    public int[] reversePrint1(ListNode head) {
        int size = listSize(head);
        int[] rev = new int[size];
        int s = size;
        //反向添加
        while(s>0){
            rev[s-1] = head.val;
            head = head.next;
            s--;
        }
        return rev;
    }
    //快慢指针求长
    public int listSize(ListNode head){
        int s = 0;
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            s++;
        }
        if(fast!=null){
            return 2*s+1;
        }
        return 2*s;
    }
    //法2
    public int[] reversePrint2(ListNode head) {
        int count=0;
        ListNode res = null;
        //头插法 先对链表进行逆置 并且记录head的长度
        while(head!=null){
            ListNode cur = head.next;
            head.next = res;
            res = head;
            head = cur;
            count++;
        }
        //创建数组  将res的值存储进arr
        int[] arr = new int[count];
        for(int i = 0; i < count; i++){
            arr[i] = res.val;
            res = res.next;
        }
        return arr;
    }
    //法3递归
    int[] ret;
    int i = 0;
    int j = 0;
    public int[] reversePrint(ListNode head) {
        solve(head);
        return ret;
    }
    public void solve(ListNode head){
        if(head==null){
            ret = new int[i];
            return;
        }
        i++;
        solve(head.next);
        ret[j] = head.val;
        j++;
    }
    //法4辅助栈
    public int[] reversePrint4(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head!=null){
            stack.push(head.val);
            head = head.next;
        }
        int[] ret = new int[stack.size()];
        for(int i = 0;i<ret.length;i++){
            ret[i] = stack.pop();
        }
        return ret;
    }
}
